// 题目：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
// 题解：https://shentuzhigang.blog.csdn.net/article/details/118469014

package main

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	len1, len2 := len(nums1), len(nums2)
	len := len1 + len2
	if len1 > len2 {
		return findMedianSortedArrays(nums2, nums1)
	}
	if len1 == 0 {
		if len2%2 != 0 {
			return float64(nums2[len2/2])
		} else {
			return float64(nums2[len2/2-1]+nums2[len2/2]) / 2.0
		}
	}
	l := 0
	r := len1
	for l <= r {
		cur1 := l + (r-l)/2
		cur2 := (len+1)/2 - cur1
		var L1, R1, L2, R2 int
		if cur1 == 0 {
			L1 = -1e10
		} else {
			L1 = nums1[cur1-1]
		}
		if cur1 == len1 {
			R1 = 1e10
		} else {
			R1 = nums1[cur1]
		}
		if cur2 == 0 {
			L2 = -1e10
		} else {
			L2 = nums2[cur2-1]
		}
		if cur2 == len2 {
			R2 = 1e10
		} else {
			R2 = nums2[cur2]
		}
		if R1 < L2 {
			l = cur1 + 1
		} else if L1 > R2 {
			r = cur1 - 1
		} else {
			if len%2 != 0 {
				return float64(max(L1, L2))
			} else {
				return float64(max(L1, L2)+min(R1, R2)) / 2.0
			}
		}
	}
	return 0
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}
